package com.douma.第23天;

import java.util.Scanner;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class 猴子爬山 {
    // 这个是斐波那契数问题的变形问题，这道题目是动态规划的经典题目
    // 请学习课程 B【刷题篇第 26 天：动态规划（一）】 第 2 节, 链接：https://yjs.xet.tech/s/3ZJm6m
    // 同时，请学习课程 B【刷题篇第 27 天：动态规划（二）】 第 2 节, 链接：https://yjs.xet.tech/s/2mALLp
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if (n <= 1) {
            System.out.println(n);
            return;
        }

        // 1. 状态 dp[i]：表示走到第 i 个台阶的方法数
        int[] dp = new int[n + 1];

        // 2. 状态初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;

        // 3. 状态转移
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }

        // 4. 返回最终需要的状态值
        System.out.println(dp[n]);

        sc.close();
    }
}
